#pragma once

// 输入数组array和数组长度size
// array数组必须是凹的
template<typename T>
int trichotomy_min(T *array, size_t size) {
    double left = 0, right = double(size) - 0.1;
    double p1, p2;
    while (right - left > 0.1) {
        double margin = (right - left) / 3;
        p1 = left + margin;
        p2 = p1 + margin;
        if (array[int(p1)] > array[int(p2)])
            left = p1;
        else
            right = p2;
    }
    return int((left + right) / 2);
}

template<typename T>
int trichotomy_max(T *array, size_t size) {
    double left = 0, right = double(size) - 0.1;
    double p1, p2;
    while (right - left > 0.1) {
        double margin = (right - left) / 3;
        p1 = left + margin;
        p2 = p1 + margin;
        if (array[int(p1)] < array[int(p2)])
            left = p1;
        else
            right = p2;
    }
    return int((left + right) / 2);
}

// 三分搜索算法
// 输入数组array, 数组长度size, 搜索字段key, 返回搜索成功index
// array必须是凹的
template<typename T>
int trichotomy_min_search(T *array, size_t size, T &key) {
    double left = 0, right = double(size) - 0.1;
    double p1, p2;
    while (right - left > 0.1) {
        if (array[int(left)] == key)
            return int(left);
        if (array[int(right)] == key)
            return int(right);

        double margin = (right - left) / 3;
        p1 = left + margin;
        p2 = p1 + margin;
        if (array[int(p1)] > array[int(p2)])
            left = p1;
        else
            right = p2;
    }
    return -1; // 搜索失败
}